package q464_canIWin;

public class Solution_1 {
    boolean[] vis;
    int maxChoosableInteger, desiredTotal;

    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        this.maxChoosableInteger = maxChoosableInteger;
        this.desiredTotal = desiredTotal;
        for (int i = 1; i <= maxChoosableInteger; i++) {
            vis = new boolean[21];
            vis[i] = true;
            if (dfs(i)) return true;
        }
        return false;
    }


    /**
     * @param curSum 当前已经选的数的总和
     * @return
     */
    private boolean dfs(int curSum) {
        //已经达到目标数desiredTotal，返回true
        if (curSum >= desiredTotal) return true;
        //遍历从1 到 maxChoosableInteger的每一个数
        for (int i = 1; i <= maxChoosableInteger; i++) {
            if (vis[i]) continue;//被访问过，不需要继续
            vis[i] = true;//标记
            //如果curSum+i 即对手能赢得游戏，意味着当前玩家失败
            if (dfs(curSum + i)) {
                return vis[i] = false;
            }
            vis[i] = false;//恢复
        }
        return true;
    }

}
